package day_2022_12_to_3.year2023;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author haomin
 * @date 2023/03/29 14:14
 **/
public class Day3_29_Review {
    public static final ThreadLocalRandom random = ThreadLocalRandom.current();

    public static void main(String[] args) {
        int[] arr1 = new int[1000000];
        for(int i = 0; i < arr1.length; ++i)
            arr1[i] = random.nextInt(0,1000);
        int[] arr2 = Arrays.copyOf(arr1, arr1.length);
        int[] arr3 = Arrays.copyOf(arr1, arr1.length);
        int[] arr4 = Arrays.copyOf(arr1, arr1.length);

        Long start, end;

        // quickSort1
        start = System.nanoTime();
        quickSort1(arr1, 0, arr1.length-1);
        end = System.nanoTime();
        System.out.println(isOrder(arr1) +", quickSort1 耗时：" + (end-start)/1000000.0 + "ms");

        // quickSort2
        start = System.nanoTime();
        quickSort2(arr2, 0, arr2.length-1);
        end = System.nanoTime();
        System.out.println(isOrder(arr2) +", quickSort2 耗时：" + (end-start)/1000000.0 + "ms");

        // quickSort3
        start = System.nanoTime();
        quickSort3(arr3, 0, arr3.length-1);
        end = System.nanoTime();
        System.out.println(isOrder(arr3) +", quickSort3 耗时：" + (end-start)/1000000.0 + "ms");

        // potholing
        start = System.nanoTime();
        quickSort4(arr4, 0, arr4.length-1);
        end = System.nanoTime();
        System.out.println(isOrder(arr4) +", potholing  耗时：" + (end-start)/1000000.0 + "ms");
    }

    // quickSort1
    private static void quickSort1(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partition(arr, l, r);
        quickSort1(arr, l, p - 1);
        quickSort1(arr, p + 1, r);
    }
    private static int partition(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);
        int v = arr[l];
        // arr[j..i) < v
        // arr[i..r] >= v
        int j = l;
        for(int i = l+1; i <= r; ++i) {
            if(arr[i] < v) {
                swap(arr, j+1, i);
                j++;
            }
        }
        swap(arr, l, j);
        return j;
    }

    // quickSort2
    private static void quickSort2(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partition2(arr, l, r);
        quickSort2(arr, l, p-1);
        quickSort2(arr, p+1, r);
    }
    private static int partition2(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l, r);
        swap(arr, l, randomIndex);
        int v = arr[l];
        int i = l+1;
        int j = r;
        while (true) {
            while (i <= j && arr[i] < v) i++;
            while (i <= j && arr[j] > v) j--;
            if(i >= j) break;
            swap(arr, i, j);
            i++; j--;
        }
        swap(arr, l, j);
        return j;
    }

    // quickSort3
    private static void quickSort3(int[] arr, int l, int r) {
        if(l >= r) return;
        int randomIndex = random.nextInt(l, r);
        swap(arr, randomIndex, l);
        int v = arr[l];
        // arr[l+1...lt] < v
        // arr[lt+1...i-1] = v
        // arr[gt....r] > v
        int lt = l;
        int gt = r+1;
        int i = l + 1;
        while (i < gt) {
            if(arr[i] < v) {
                swap(arr, lt+1, i);
                lt++; i++;
            }else if(arr[i] > v) {
                swap(arr, gt-1, i);
                gt--;
            }else i++;
        }
        swap(arr, l, lt);
        quickSort3(arr, l, lt);
        quickSort3(arr, gt, r);
    }

    private static void quickSort4(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partition4(arr, l, r);
        quickSort4(arr, l, p - 1);
        quickSort4(arr, p + 1, r);
    }
    private static int partition4(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l, r);
        swap(arr, randomIndex, l);
        int v = arr[l];
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= v) j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= v) i++;
            arr[j] = arr[i];
        }
        arr[i] = v;
        return i;
    }




    private static boolean isOrder(int[] arr) {
        for(int i = 0; i < arr.length-1; ++i)
            if(arr[i] > arr[i + 1]) return false;
        return true;
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    class Solution1 {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null) return root;
            TreeNode l = root.left;
            TreeNode r = root.right;
            root.left = r;
            root.right = l;
            mirrorTree(root.left);
            mirrorTree(root.right);
            return root;
        }
    }

    class Solution2 {
        public boolean isSymmetric(TreeNode root) {
            if(root == null) return true;
            return isSymmetricHelper(root.left, root.right);
        }
        private boolean isSymmetricHelper(TreeNode l, TreeNode r) {
            if(l == null && r == null) return true;
            if(l == null || r == null) return false;
            return l.val == r.val && isSymmetricHelper(l.left, r.right) && isSymmetricHelper(l.right, r.left);
        }
    }

    class MinStack3 {
        Deque<Integer> s1;
        Deque<Integer> s2;

        /** initialize your data structure here. */
        public MinStack3() {
            s1 = new LinkedList<>();
            s2 = new LinkedList<>();
        }

        public void push(int x) {
            s1.push(x);
            if(s2.isEmpty()) s2.push(x);
            else s2.push(s2.peek() > x ? x : s2.peek());
        }

        public void pop() {
            s1.pop();
            s2.pop();
        }

        public int top() {
            return s1.peek();
        }

        public int min() {
            return s2.peek();
        }
    }
}